/*
 * p22.h
 *
 *  Created on: 28/gen/2011
 *      Author: dustgod
 */

#include <string>
#include <iostream>

using namespace std;

const int OFFSET = (int)('A')-1;

class Nome {
public:
	string n;
	int value;
	Nome(string);
	bool operator<(const Nome &) const;
};

Nome::Nome(string s) {
	n = s;
	value = 0;
	for(int i=0;i<n.size();i++)
		value += (int)n[i] - OFFSET;
}

// Confronto alfanumerico. Funziona solo se i nomi sono entrambi tutti lowercase o uppercase.
bool Nome::operator<(const Nome &nome) const {
	int max;
	if(this->n.size()<nome.n.size())
		max = this->n.size();
	else
		max = nome.n.size();
	for(int i=0;i<max;i++){
		if(this->n[i]<nome.n[i])
			return true;
		else
			if(this->n[i]>nome.n[i])
				return false;
	}
	if(this->n.size()<nome.n.size())
		return true;
	else
		return false;
}

void scambia(Nome* &n1,Nome* &n2) {
	Nome* buffer = n1;
	n1 = n2;
	n2 = buffer;
}

int alphanumericPartition(Nome** &v,int p,int r) {
	Nome* pivot = v[r];
	int i = p-1;
	for(int j=p;j<r;j++)
		if(*v[j]<*pivot)
			scambia(v[++i],v[j]);
	scambia(v[i+1],v[r]);
	return i+1;
}

/*
	ATTENZIONE: questo algoritmo per il QuickSort va chiamato con
		alphanumericQuickSort(v,0,v.length()-1)
	per evitare che vada in Segmentation Fault.
 */
void alphanumericQuickSort(Nome** &v,int p,int r) {
	int q;
	if(p<r){
		q = alphanumericPartition(v,p,r);
		alphanumericQuickSort(v,p,q-1);
		alphanumericQuickSort(v,q+1,r);
	}
}
